package dataStruct.graph;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

/**
 * Created by thinkpad on 2016/3/20.
 */
public class Graph {
    public Graph(List<String> node, ConcurrentMap<AsKey, Long> asMap) {
        this.nodes = node;
        this.asMap = asMap;
    }

    public List<String> nodes;
    public ConcurrentMap<AsKey, Long> asMap;
    private ConcurrentMap<AsKey, Long> distMap = new ConcurrentHashMap<AsKey, Long>();
    private ConcurrentMap<AsKey, String> pathMap = new ConcurrentHashMap<AsKey, String>(); //ASkey, the nearst to the dstNode
    private List<String> hasFindShortPaths = new ArrayList<String>();

    public void shortPath(String srcNode) {
        for (String dstNode: nodes) {
            AsKey asKey = new AsKey(srcNode, dstNode);
            distMap.put(asKey, asMap.get(new AsKey(srcNode, dstNode)));
            if(distMap.get(asKey) < Long.MAX_VALUE) {
                pathMap.put(asKey, srcNode);
            }
        }

        hasFindShortPaths.add(srcNode);

        for (int count = 1; count <= nodes.size()-1; count++) {
            Long wm = Long.MAX_VALUE;
            String currentShortestNodeInDistMap = srcNode;
            for (String dstNode: nodes) {
                if(!hasFindShortPaths.contains(dstNode)&&distMap.get(new AsKey(srcNode, dstNode))<wm) {
                    wm = distMap.get(new AsKey(srcNode, dstNode));
                    currentShortestNodeInDistMap = dstNode;
                }
            }
            hasFindShortPaths.add(currentShortestNodeInDistMap);
            for(String dstNodeDirectToCurrentShortestNodeInDistMap: nodes) {
                Long currentShortestDistInDistMap = distMap.get((new AsKey(srcNode, currentShortestNodeInDistMap)));
                Long distToDstNode = asMap.get(new AsKey(currentShortestNodeInDistMap, dstNodeDirectToCurrentShortestNodeInDistMap));
                Long distSrcToDst = distMap.get(new AsKey(srcNode, dstNodeDirectToCurrentShortestNodeInDistMap));
                if(null != currentShortestDistInDistMap && null != distToDstNode && null !=distSrcToDst) {
                    if(!hasFindShortPaths.contains(dstNodeDirectToCurrentShortestNodeInDistMap)&&!currentShortestDistInDistMap.equals(Long.MAX_VALUE)&&
                            !distToDstNode.equals(Long.MAX_VALUE)&&currentShortestDistInDistMap + distToDstNode < distSrcToDst) {
                        distMap.put(new AsKey(srcNode, dstNodeDirectToCurrentShortestNodeInDistMap), currentShortestDistInDistMap + distToDstNode);
                        pathMap.put(new AsKey(srcNode, dstNodeDirectToCurrentShortestNodeInDistMap), currentShortestNodeInDistMap);
                    }
                }
            }
        }

        //输出结果
        for (String outPutNode: nodes) {
            StringBuffer outPutStr = new StringBuffer();
            if(hasFindShortPaths.contains(outPutNode)) {
                String tempDstNode = outPutNode;
                while (!tempDstNode.equals(srcNode)) {
//                    System.out.println(tempDstNode + "<-");
                    outPutStr.append(tempDstNode).append("<-");
                    tempDstNode = pathMap.get(new AsKey(srcNode, tempDstNode));
                }
                outPutStr.append(srcNode).append("     ").append(distMap.get(new AsKey(srcNode, outPutNode)));
//                System.out.println(srcNode+"     "+distMap.get(new AsKey(srcNode, outPutNode)));
                System.out.println(outPutStr);
            } else {
                System.out.println("No Path          MAX ");
            }
        }
    }
}
